#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lc c<<1
#define rc c<<1|1
const int N = 4e5+5;
int n,m;
ll a[N],b[N],S,C;
bool vis[N];
int trc[N];
ll trs[N];
ll G(int x)
{
    ll sum = 0;
    int cur = 0;
    for(int i = 19;i >= 0;i--) if((cur + (1<<i)) <= m && trc[cur+(1<<i)] <= x)
    {
        cur += (1<<i);
        x -= trc[cur];
        sum += trs[cur];
    }
    return sum;
}
ll F(int x){return G(x+1) - (S-G(C-x));}
struct Node{
    __int128 sum,cnt,res;
};
Node operator + (Node i,Node j){return Node{i.sum + j.sum,i.cnt + j.cnt,i.res + j.res + i.sum*j.cnt};}
struct SGT{
    Node tr[N<<2],ftr[N<<2];
    void Upd(int c,int l,int r,int x,int y)
    {
        //cout<<"?"<<c<<" "<<l<<" "<<r<<" "<<x<<" "<<y<<"\n";
        if(l == r) return tr[c].cnt += y,tr[c].sum += y*b[x],tr[c].res += y*b[x],ftr[c] = tr[c],void();
        int mid = (l+r>>1);
        if(x <= mid) Upd(lc,l,mid,x,y);
        else Upd(rc,mid+1,r,x,y);
        tr[c] = tr[lc] + tr[rc];
        ftr[c] = ftr[rc] + ftr[lc];
    }
    Node Qry(int c,int l,int r,int x)
    {
        if(l == r) return Node{x*b[l],x,x*b[l]};
        int mid = (l+r>>1);
        if(tr[lc].cnt <= x) return tr[lc] + Qry(rc,mid+1,r,x-tr[lc].cnt);
        else return Qry(lc,l,mid,x);
    }
    Node Qry2(int c,int l,int r,int x)
    {
        //cout<<"!"<<c<<" "<<l<<" "<<r<<" "<<x<<" "<<ll(ftr[rc].cnt)<<"\n";
        if(l == r) return Node{x*b[l],x,x*b[l]};
        int mid = (l+r>>1);
        if(ftr[rc].cnt <= x) return ftr[rc] + Qry2(lc,l,mid,x-ftr[rc].cnt);
        else return Qry2(rc,mid+1,r,x);
    }
}t;
__int128 preF(int x){return (t.Qry(1,1,m,x+1)).res - (t.Qry2(1,1,m,x)).res;}
int lowbit(int x){return x&(-x);}
void upd(int x,int y)
{
    t.Upd(1,1,m,x,y);
    for(int c = x;c <= m;c += lowbit(c)) trc[c]+=y,trs[c]+=y*b[x];
}
int main()
{
    freopen("kte.in","r",stdin);
    freopen("kte.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n;
    for(int i = 1;i <= n;i++) cin>>a[i],b[i] = a[i];
    sort(b+1,b+1+n);
    m = unique(b+1,b+1+n)-b-1;
    for(int i = 1;i <= n;i++)
    {
        int x = lower_bound(b+1,b+1+m,a[i])-b;
        if(vis[x]) vis[x] = 0,S -= a[i],upd(x,-1),C--;
        else vis[x] = 1,S += a[i],upd(x,1),C++;
        //if(i != 3) continue;
        if(C == 0)
        {
            cout<<"0\n";
            continue;
        }
        int L = 1,R = (C-1)/2+1;
        //cout<<L<<" "<<R<<"\n";
        while(L < R)
        {
            int mid = (L+R>>1);
            if(F(mid) < 0) R = mid;
            else L = mid+1;
        }
        //cout<<L<<"\n";
        __int128 ans = S;
        ans -= preF(L-1);
        L = (C-1)/2+1,R = C;
        //cout<<L<<" "<<R<<"\n";
        while(L < R)
        {
            int mid = (L+R>>1);
            if(F(mid) >= 0) R = mid;
            else L = mid+1;
        }
        ans -= preF(C-1) - preF(L-1);
        cout<<ll(ans)<<"\n";
    }
    //cerr<<clock()<<"\n";
    return 0;
}